Junior programmer Sasha
wrote his first testing system. He was so happy to compile it that he decided
to invite school friends to his own contest.
But at the end of the
contest, it became clear that the system couldn’t sort the teams
in the results table. Help Sasha implement this sort.
The teams are ordered
according to ACM rules:
·
by the number of solved tasks in descending order;
·
if the number of solved problems is equal, sort by the
penalty time in ascending order;
·
if all the previous parameters are equal, sort by the team
number in ascending order.
Input. The first line contains the number of teams n (1 ≤ n ≤ 100000) that take part in the contest. The i-th of the next n lines contains the number of solved problems s (0 ≤ s ≤
100) and the penalty time t (0
≤ t ≤ 100000) for the
team with number i.
Output. Print n numbers –
the team numbers in the sorted order.
|
Sample
input |
Sample
output |
|
5 3 50 5 720 1 7 0 0 8 500 |
5 2 1 3 4 |
sort
We will store
the team in a structure:
·
team number;
·
penalty time;
·
the number of solved problems;
It is necessary to write a comparator – a function for comparing two teams
of participants. Then sort the teams.
Declare the structure of
the team – participant in the ACM contest: team number, penalty time, and
number of solved problems.
struct person
{
int id,
penalty_time, problems;
} *acm;
Function cmp
is a comparator for sorting the participants in a competition.
int cmp(person a, person b)
{
Sort by the number of solved tasks in descending order.
if
(a.problems != b.problems) return a.problems
> b.problems;
If the number of solved problems is equal, sort by the penalty time in
ascending order.
if
(a.penalty_time != b.penalty_time)
return a.penalty_time
< b.penalty_time;
If all the previous parameters are equal, sort by the team number in
ascending order.
return a.id
< b.id;
}
The main part of the
program. Allocate memory for an array of teams.
scanf("%d",&n);
acm = new person[n];
Read the information about the teams.
for(i = 0; i < n; i++)
{
scanf("%d
%d",&acm[i].problems,&acm[i].penalty_time);
acm[i].id = i + 1;
}
Sort the teams according to the given condition.
sort(acm,acm+n,cmp);
Print the team’s IDs in the order of their locations in the resulting table.
for(i = 0; i < n; i++)
printf("%d ",acm[i].id);
printf("\n");
delete[] acm;
#include <cstdio>
#include <algorithm>
using namespace std;
int n, i, ptr;
struct person
{
int id, penalty_time,
problems;
int operator< (const
person &a) const
{
if
(problems != a.problems) return problems >
a.problems;
if
(penalty_time != a.penalty_time)
return
penalty_time < a.penalty_time;
return id
< a.id;
}
} *acm;
int main(void)
{
scanf("%d",&n);
acm = new
person[n];
for(i = 0; i
< n; i++)
{
scanf("%d
%d",&acm[i].problems,&acm[i].penalty_time);
acm[i].id = i + 1;
}
sort(acm,acm+n);
for(i = 0; i
< n; i++)
printf("%d
",acm[i].id);
printf("\n");
delete[] acm;
return 0;
}
Java realization
import java.util.*;
class Person
{
int problems;
int penalty_time;
int id;
public Person(int problems, int penalty_time, int id)
{
this.problems = problems;
this.penalty_time = penalty_time;
this.id = id;
}
}
public class Main
{
public static class MyFun implements Comparator<Person>
{
public int compare(Person a, Person b)
{
if (a.problems == b.problems && a.penalty_time == b.penalty_time) return a.id - b.id;
if (a.problems == b.problems) return a.penalty_time - b.penalty_time;
return b.problems - a.problems;
}
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
Person[] p = new Person[n];
for (int i = 0; i < n; i++)
p[i] = new Person(con.nextInt(), con.nextInt(), i+1);
Arrays.sort(p, new MyFun());
for (int i = 0; i < n; i++)
System.out.print(p[i].id + " ");
con.close();
}
}